#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 505;
const int M = 1e4 + 5;
int n, m;
int head[N];
int ver[M << 1], Next[M << 1], tot;
void add(int u, int v) {
  ++tot;
  ver[tot] = v;
  Next[tot] = head[u];
  head[u] = tot;
}
struct Node {
  int x, y, z;
};
int dis[N][N][2];
Node pre[N][N][2];
void bfs() {
  memset(dis, -1, sizeof(dis));
  dis[1][n][0] = 0;
  queue<Node> q;
  q.push(Node{1, n, 0});
  while (q.size()) {
    Node now = q.front();
    q.pop();
    int x = now.x, y = now.y, z = now.z;
    if (!z) {
      for (int i = head[x]; i; i = Next[i]) {
        int x2 = ver[i];
        if (dis[x2][y][1] == -1) {
          pre[x2][y][1] = now;
          dis[x2][y][1] = dis[x][y][0] + 1;
          q.push(Node{x2, y, 1});
        }
      }
    } else {
      for (int i = head[y]; i; i = Next[i]) {
        int y2 = ver[i];
        if (y2 == x) continue;
        if (dis[x][y2][0] == -1) {
          pre[x][y2][0] = now;
          dis[x][y2][0] = dis[x][y][1] + 1;
          q.push(Node{x, y2, 0});
        }
      }
    }
  }
}
void solve() {
  cin >> n >> m;
  rep(i, 1, m) {
    int u, v;
    cin >> u >> v;
    add(u, v), add(v, u);
  }
  bfs();
  if (dis[n][1][0] == -1) {
    cout << -1;
    return;
  }
  cout << dis[n][1][0] / 2 << endl;
  vector<pii> res;
  int x = n, y = 1, z = 0;
  while (x != 0 && y != 0) {
    if (!z) res.push_back(pii(x, y));
    Node p = pre[x][y][z];
    x = p.x, y = p.y, z = p.z;
  }
  reverse(res.begin(), res.end());
  for (pii p : res) cout << p.first << ' ';
  cout << endl;
  for (pii p : res) cout << p.second << ' ';
  return;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t = 1;
  while (t--) solve();
  return 0;
}